with \epsilon = 0.9. Recall that we showed that the Relaxation Method (x_{n+1} = x_n - \lambda f(x_n)) converged linearly with asymptotic error constant \left| 1 - 0.1 \lambda \right| and Newton’s Method converged faster than quadratically. For the remainder of this question, fix \epsilon = 1. Here’s a plot of f:
First notice that f(2\pi) = 2\pi - \sin2\pi - 2\pi = 0. We will use the fact that | \sin x | < |x| for all x \not= 0. Using the fact that \sin is 2\pi-periodic, we have
┌ Warning: max interations with |f| = 2.5345819611999332e-5
└ @ Main In[22]:35
This iteration seems to converge very slowly and the computed order of convergence seems to appoach 1. However, since \mu also approaches 1, we have sub-linear convergence.
💻 Show numerically that Newton’s method converges. What is the order of convergence?
Answer.
Here is the code for Newton’s method starting at x_1 = 6.
y =Newton(f, df, 6.);orderOfConvergence( y, 2π, α =1)
The iteration seems to converge linearly with asymptotic error constant \mu = \frac{2}3.
✍ Compare your answers to this question to the \epsilon = 0.9 case. Why is the convergence slower/faster?
Answer.
In lectures, we saw that, if | g'(\xi) | < 1, and |x_1 - \xi| is sufficiently small then the simple iteration x_{n+1} = g(x_n) converges at least linearly with asymptotic erorr constant \mu = |g'(\xi)|. We are considering g(\psi) = \psi - \lambda f(\psi) with f(\psi) = \psi - \epsilon \sin \psi - 2\pi. We see that |g'(2\pi)| = | 1 - \lambda( 1 - \epsilon) |. Therefore, in the \epsilon = 0.9 case we have linear convergence whenever |1 - 0.1 \lambda | < 1. However, when \epsilon = 1, we get |g'(2\pi)| = 1 and sublinear convergence.
In lectures, we saw that if f : [a,b] \to \mathbb R is twice continuously differentiable with f(\xi) = 0 and f'(\xi) \not= 0, then the Newton iteration converges at least quadratically to \xi for all x_1 sufficiently close to \xi. We have f'(2\pi) = 1 - \epsilon so f'(2\pi) \not= 0 when \epsilon = 0.9 but f'(2\pi) = 0 when \epsilon = 1.
This means that, for \xi = 2\pi, we have f(\xi) = f'(\xi) = f''(\xi) = 0 but f'''(\xi) \not= 0. In this case, there exists an interval a< \xi < b and m > 0 such that m < |f'''(x)| < 2m for all x \in [a,b]. Therefore, for x_n \in [a,b], there exists \eta_n, \theta_n between x_n and \xi for which
Here, we have used the fact that \frac13 = 1 -\frac{1}3\frac{2m}{m} \leq 1-\frac{1}3\frac{f'''(\eta_n)}{f'''(\theta_n)} \leq 1- \frac{1}3\frac{m}{2m} = \frac56. As a result, Newton’s iteration starting in [a,b] converges linearly with asymptotic error constant
In general, if \xi is a root of f of multiplicity m and f^{(m)} is continuous (and f^{(m)}(\xi) \not=0), then one can find an interval [a,b] around \xi for which Newton’s iteration converges linearly to \xi for all x_1 \in [a,b] and the asymptotic error constant is \mu = \frac{m-1}{m} (can you prove this?).
24.2 D. Research Task
Find a research paper explaining a method named after one of the following people: Halley, Householder, Osada, Ostrowski, Steffensen, Traub. What is the main novelty of this method? How does it (claim to) improve upon previous methods in the literature? Implement your chosen method and test it on a function of your choice.
Please clearly cite which paper you are describing.
There are many possible answers! Let me know if you want to present your answer to the rest of the class (see Syllabus for grading info).
